This invention relates generally to troubleshooting program code, and more specifically to methods and apparatus for detecting memory leakage in linked lists contained in a running program.
A common problem in software development is memory leaks. A memory leak occurs when a program or an application reserves a piece of memory within a program heap (generally through malloc( ) or new( ) intrinsic calls, depending on the program language), loses track of the fact that the program has reserved this piece of memory, and never frees up the reserved piece of memory. If the program fails to properly release reserved memory enough times during execution of the program, the programming language will keep growing in memory size and will eventually die as the system runs out of memory to give to the running program. This type of program error is known as a “memory leak.”
There are several tools available, e.g., Insure™ (by Parasoft) and Purify™ (by Rational Software), that can be run in conjunction with a program to determine if the program has memory leaks. These tools look for cases where a piece of memory is assigned within a function to a local pointer variable. As this same piece of memory is assigned to other variables, a reference count is maintained and a database is updated with the location in the program's source code where each reference occurs. When a variable that has reference to the piece of memory either gets reassigned or is no longer in scope due to a function return, the reference count of the piece of memory is checked to make sure that some other variable still has reference to that piece of memory.
The programmer must explicitly include code in the program to free the piece of memory (often by calling a free( ) intrinsic) when the program is finished with that piece of memory. Once the piece of memory has been freed, the piece of memory is returned to the program heap for re-use by the program. If, however, there are no longer any variables referencing the piece of memory and the piece of memory has not been explicitly freed, the piece of memory is considered leaked. Tools such as Insure™ and Purify™ will report the leak, thus allowing the programmer to track the leak down and rectify the problem.
However, there is another kind of leak that tools such as Insure™ and Purify™ cannot find. These are leaks that occur in linked lists. Most programs today make use of linked list data structures. A linked list is a data structure that allows new elements to be added and linked to the existing list. Queues and stacks are common uses for linked lists, but databases can also be implemented using several linked lists. A file system might also use linked lists, employing the linked lists in a hierarchical manner. Linked lists contain a head pointer that references the first (or last) element in the linked lists. Linked elements also contain “next” pointers, which reference the next element in the list.
The problem with using tools such as Insure™ and Purify™ to find leaks in linked lists is that these tools cannot not deal with situations where there is still some reference to the memory, as with linked lists. As long as there is a reference to the head pointer, there is a reference to the entire linked list and memory leak tools such as Insure™ and Purify™ will not consider any elements in the list as “leaked”. However, if the program's code continues to add elements to the linked list without explicitly removing them after they are no longer needed, the linked list will have a leak.
What is needed is a tool that will detect a memory leak in a linked list even though the leaked piece of memory is still being referenced by some variable in the running program.